package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/7/7 13:04
 * @Version 1.0
 **/
public class BinaryTreeLevelOrderTraversalII {

    /**
     * 暴力解法：使用层序遍历的原理，给Node加上一个Layer的标志，使用layer作为List的下标，最后反转List
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedBlockingQueue<TagTreeNode> queue = new LinkedBlockingQueue<TagTreeNode>();
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) {
            queue.add(new TagTreeNode(root, 1));
        } else {
            return result;
        }
        TagTreeNode temp;
        TreeNode tempNode;
        int layer;
        List<Integer> layerNums = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            layer = temp.getLayer();
            tempNode = temp.getNode();
            if (result.size() < layer) {
                layerNums = new ArrayList<>();
                layerNums.add(tempNode.val);
                result.add(layerNums);
            } else {
                layerNums = result.get(layer - 1);
                layerNums.add(tempNode.val);
            }
            if (tempNode.left != null) {
                queue.add(new TagTreeNode(tempNode.left, layer + 1));
            }
            if (tempNode.right != null) {
                queue.add(new TagTreeNode(tempNode.right, layer + 1));
            }
        }
        Collections.reverse(result);
        return result;

    }

    class TagTreeNode {
        TreeNode node;
        int layer;

        public TagTreeNode() {
        }

        public TagTreeNode(TreeNode node, int layer) {
            this.node = node;
            this.layer = layer;
        }

        public TreeNode getNode() {
            return node;
        }

        public void setNode(TreeNode node) {
            this.node = node;
        }

        public int getLayer() {
            return layer;
        }

        public void setLayer(int layer) {
            this.layer = layer;
        }
    }
}
